package linkedlist;

import java.util.ArrayList;
import java.util.Collections;

import datastructure.ListNode;
/**
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 */
public class E21_MergeTwoSortedLists {
    /**
     * 时间复杂度 O(m+n) 空间复杂度 O(1)
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode(0);
        ListNode dummyNode = dummyHead;
        ListNode list1Node = list1;
        ListNode list2Node = list2;

        while (list1Node != null && list2Node != null) {
            if (list1Node.val > list2Node.val) {
                dummyNode.next = list2Node;
                list2Node = list2Node.next;
            } else {
                dummyNode.next = list1Node;
                list1Node = list1Node.next;
            }
            dummyNode = dummyNode.next;
        }
        if (list1Node == null) dummyNode.next = list2Node;
        if (list2Node == null) dummyNode.next = list1Node;
        //dummyNode = list1Node == null ? list2Node : list1Node;
        return dummyHead.next;
    }
    /**
     * 递归
     * 时间复杂度 O(m+n) 空间复杂度 O(m+n)
     */
    public static ListNode mergeTwoLists1(ListNode list1, ListNode list2) {
        // 边际处理与递归出口
        if (list1 == null) return list2;
        if (list2 == null) return list1; 

        if (list1.val > list2.val) {
            list2.next = mergeTwoLists1(list1, list2.next);
            return list2;
        } else {
            list1.next = mergeTwoLists1(list1.next, list2);
            return list1;
        }
    }
    /**
     * (不推荐)为了AC而AC (AC == Accepted)
     * 时间复杂度 O(m+n) 空间复杂度 O(m+n)
     */
    public ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode(0);
        ListNode dummyNode = dummyHead;
        ListNode list1Node = list1;
        ListNode list2Node = list2;
        ArrayList<Integer> arrayList = new ArrayList<>();

        // 将list1和list2的数据存放在arrayList中
        while (list1Node != null) {
            arrayList.add(list1Node.val);
            list1Node = list1Node.next;
        }
        while (list2Node != null) {
            arrayList.add(list2Node.val);
            list2Node = list2Node.next;
        }
        // 混合后排序
        Collections.sort(arrayList);
        // 存放在链表中
        for (Integer integer : arrayList) {
            dummyNode.next = new ListNode(integer);
            dummyNode = dummyNode.next;
        }
        return dummyHead.next;
    }
}
